//给定一个二维网格和一个单词，找出该单词是否存在于网格中。 
//
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 
//
// 
//
// 示例: 
//
// board =
//[
//  ['A','B','C','E'],
//  ['S','F','C','S'],
//  ['A','D','E','E']
//]
//
//给定 word = "ABCCED", 返回 true
//给定 word = "SEE", 返回 true
//给定 word = "ABCB", 返回 false 
//
// 
//
// 提示： 
//
// 
// board 和 word 中只包含大写和小写英文字母。 
// 1 <= board.length <= 200 
// 1 <= board[i].length <= 200 
// 1 <= word.length <= 10^3 
// 
// Related Topics 数组 回溯算法 
// 👍 539 👎 0

package leetcode.editor.cn;

//Java：单词搜索
public class P79WordSearch {

    /**
     * 思路：回溯法，找出每个点的邻点，然后搜索相邻点，如果没有值 就回溯
     * <p>
     * 执行用时： 52 ms , 在所有 Java 提交中击败了 7.57% 的用户 内存消耗： 40.6 MB , 在所有 Java 提交中击败了 97.04% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean exist(char[][] board, String word) {
            int m = board.length;
            int n = board[0].length;
            boolean[][] used = new boolean[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    used[i][j] = true;
                    if (dfs(i, j, 0, word, board, used)) {
                        return true;
                    }
                    used[i][j] = false;
                }
            }
            return false;

        }

        /**
         * 描述： 回溯搜索
         *
         * @param x     当前查找到的点的第x+1行
         * @param y     当前查找到的点的第y+1列
         * @param i     当前待查找的单词的第i个字符下标
         * @param word  待查找的单词
         * @param board 网格
         * @param used  使用标识，用来判断重复
         * @return "boolean"
         * @date: 2020/9/1 11:09
         */
        private boolean dfs(int x, int y, int i, String word, char[][] board, boolean[][] used) {
            char ch = board[x][y];
            if (word.charAt(i++) != ch) {
                return false;
            }
            if (i >= word.length()) {
                return true;
            }

            // 周围的四格 的坐标
            int[][] adj = getAdj(x, y, board);

            for (int[] index : adj) {
                int a = index[0];
                int b = index[1];
                if (a == -1 || b == -1 || used[a][b]) {
                    continue;
                }
                used[a][b] = true;

                if (dfs(a, b, i, word, board, used)) {
                    return true;
                }
                used[a][b] = false;
            }
            return false;
        }

        /**
         * 描述：找出当前点的上下左右四个邻点，如果超出网格，则设置-1
         *
         * @param x     当前点下标
         * @param y     当前点下标
         * @param board 网格
         * @return "int[][]"
         * @date: 2020/9/1 11:11
         */
        private int[][] getAdj(int x, int y, char[][] board) {
            int m = board.length;
            int n = board[0].length;

            int[][] arr = new int[4][2];
            int[] temp0 = new int[2];
            int[] temp1 = new int[2];
            int[] temp2 = new int[2];
            int[] temp3 = new int[2];

            // 上
            if (x <= 0) {
                temp0[0] = -1;
            } else {
                temp0[0] = x - 1;
            }
            temp0[1] = y;

            // 下
            if (x >= m - 1) {
                temp1[0] = -1;
            } else {
                temp1[0] = x + 1;
            }
            temp1[1] = y;

            // 左
            temp2[0] = x;
            if (y <= 0) {
                temp2[1] = -1;
            } else {
                temp2[1] = y - 1;
            }

            // 右
            temp3[0] = x;
            if (y >= n - 1) {
                temp3[1] = -1;
            } else {
                temp3[1] = y + 1;
            }

            arr[0] = temp0;
            arr[1] = temp1;
            arr[2] = temp2;
            arr[3] = temp3;
            return arr;

        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        Solution solution = new P79WordSearch().new Solution();
        System.out.println(solution.exist(board, "ABCCFSADEC"));
        // TO TEST
    }

}